package com.mid;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by Lxk on 2019/6/1.
 */
public class Solution40 {

    List<List<Integer>> finalRes = new ArrayList<>();

    private void reBack(int[] candidates,int begin,int curSum,int target,List<Integer> res){
        if(curSum>=target){
            if(curSum==target){
                List<Integer> copyRes = new ArrayList<>();
                res.stream().forEach(each->copyRes.add(each));
                Collections.sort(copyRes);
                if(!finalRes.contains(copyRes)){
                    finalRes.add(copyRes);
                }
            }
            return ;
        }
        for(int i = begin;i < candidates.length; i++){
            res.add(candidates[i]);
            reBack(candidates,i+1,curSum+candidates[i],target,res);
            res.remove(res.size()-1);
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> list = new ArrayList<>();
        reBack(candidates,0,0,target,list);
        return finalRes;
    }

    public static void main(String[] args) {
        int[] arr = {10,1,2,7,6,1,5};
        Solution40 solution40 = new Solution40();
        solution40.combinationSum2(arr,8);
    }

}
